Les données sont stockées dans un fichier csv téléchargeable : fichier csv à télécharger

Voici un aperçu des données :

Voici une représentation de ces données :

Nous introduisons une nouvelle donnée (appelée cible dans notre exemple) avec ses deux caractéristiques : une force de 12 et un courage de 12,5 . Le but de l'algorithme KNN des $k$ plus proches voisins est de déterminer le type de cette nouvelle donnée.

1. Dans un premier, il faut fixer le nombre de voisins. Nous allons choisir $k$=7.

   Voici une nouvelle représentation avec la cible et la recherche des 7 voisins les plus proches proches, ceux qui se trouvent dans le cercle bleu :

   

   En utilisant les voisins de type "chevalier" et de type "fantassin", déterminer le type le plus probable de notre cible.

2. On considère désormais la valeur $=13$. Voici une nouvelle représentation avec la cible et la recherche des 13 voisins les plus proches proches, ceux qui se trouvent dans le cercle bleu : Déterminer le type le plus probable de notre cible dans ce cas ?

Nous reprenons le même ensemble de données :

Nous introduisons une cible : force = 5 et courage = 12,5

1. On choisit $k$=4 et la distance schématisée par un disque .

   

   1. Quel est le type de notre donnée cible ? Quel est le problème ?

   2. Donner une valeur de $k$ qui permette de décider du type de notre donnée cible ?

   3. Donner pour cette valeur de $k$ le type de la donnée cible.

2. On choisit $k=9$. Pour la distance, on décide que les valeurs de la force n'ont pas d'importance. La distance dépend du courage.

   

   Quel est le type de notre donnée cible ?

3. On choisit $k=5$. Pour la distance, on décide que les valeurs du courage n'ont pas d'importance. La distance dépend de la force.

   

   Quel est le type de notre donnée cible ?

1. 1. Tester le script Python suivant :

      from math import *
      import matplotlib.pyplot as plt
      
      # Données de type 1
      liste_x_1 = [1, 3, 8, 13]
      liste_y_1 = [28, 27.2, 37.6, 40.7]
      
      # Données de type 2
      liste_x_2 = [2, 3, 10, 15]
      liste_y_2 = [30, 26, 39, 35.5]
      
      plt.axis([0, 15, 0, 50]) # Attention [x1, x2, y1, y2]
      plt.xlabel('Caractéristique 1')                     # premier commentaire attendu
      plt.ylabel('Caractéristique 2')
      plt.title('Représentation des deux types')
      plt.axis('equal') # Pour avoir un repère orthonormé
      plt.grid()
      plt.scatter(liste_x_1, liste_y_1, label='type 1')    # second commentaire attendu
      plt.scatter(liste_x_2, liste_y_2, label='type 2')
      plt.legend()
      plt.show()
      

   2. Remplacer les deux commentaires attendus par un commentaire expliquant le rôle des fonctions plt.label et plt.scatter.

2. 1. Vous pouvez ajouter des formes (rectangle, ellipse, etc.).

      Exécuter le script suivant :

      from math import *
      import matplotlib.pyplot as plt
      
      # Données de type 1
      liste_x_1 = [1, 3, 8, 13]
      liste_y_1 = [28, 27.2, 37.6, 40.7]
      
      # Données de type 2
      liste_x_2 = [2, 3, 10, 15]
      liste_y_2 = [30, 26, 39, 35.5]
      
      fig, ax = plt.subplots()
      
      plt.axis([0, 15, 0, 50]) # Attention [x1, x2, y1, y2]
      plt.xlabel('Caractéristique 1')
      plt.ylabel('Caractéristique 2')
      plt.title('Représentation des deux types')
      plt.axis('equal') # pour avoir un repère orthonormé. Faire des tests.
      plt.grid()
      plt.scatter(liste_x_1, liste_y_1, label='type 1')
      plt.scatter(liste_x_2, liste_y_2, label='type 2')
      plt.legend()
      
      # Ajout d'un cercle (ou d'une ellipse)
      ax.add_artist(plt.Circle((6, 30), 4, edgecolor='b', facecolor='none'))
      
      # Ajout d'un rectangle
      ax.add_artist(
          plt.Rectangle((6, 0), 2, 50,
                            edgecolor='black', facecolor='none',
                            fill=True, hatch='/', linestyle='dashed',
                            linewidth=3, zorder=1))
      
      plt.show()
      

   2. Quel est le rôle du premier argument (6, 30) de la fonction plt.Circle ?

   3. Quel est le rôle des trois premiers arguments (6, 0), 2 et 50 de la fonction plt.Rectangle ?

Sur un champ de bataille de la Première Guerre Mondiale un mémorial a été construit. Afin de réaliser une extension, des fouilles préventives ont été réalisées par l'INRAP (Institut National de Recherches Archéologiques Préventives).
Au cours de ces fouilles, différents objets ou éléments de squelettes humains ont été trouvés. L'étude de ces découvertes a permis d'identifier la nationalité de nombreux artefacts retrouvés : soit allemand, anglais ou français.
Le plan ci-dessous représente la zone de fouille et la position des éléments dont l'origine a été identifiée. L'unité est le mètre.

Un élément d'un squelette a été retrouvé en $(10;4)$ ; il est représenté par un losange couleur magenta sur le plan.
L'objectif est de déterminer une origine probable pour cet élément de squelette avant de le déposer dans un ossuaire.

La distance qui sera prise en compte est la distance dite de Tchebychev. (la définition précise de celle-ci sera donnée au 2.)
Ce que vous devez seulement savoir sur cette distance pour cet exercice c'est que l'ensemble des points se trouvant à une distance $r$ d'un point $I$ correspond au pourtour du carré, de centre $I$, de côtés parallèles aux axes et de longueurs $2r$.
Sur le graphique ci-dessus, le carré dessiné :

• en rouge correspond ainsi à l'ensemble des points se trouvant à 3 mètres.

• en noir correspond ainsi à l'ensemble des points se trouvant à 1 mètre.

1. 1. À quelle valeur de $k$ correspond le carré noir ?

   2. Quelle serait l'origine de l'élément de squelette en considérant cette valeur de $k$ ?

2. On choisit $k=9$. Quelle serait l'origine de l'élément de squelette en considérant cette valeur de $k$ ?

3. On choisit $k=11$. Quelle serait l'origine de l'élément de squelette en considérant cette valeur de $k$ ?

4. Peut-on savoir à coup sûr, en prenant une valeur de $k$ inférieure au égale à 11, si le combattant dont on a trouvé un élément de squelette était un combattant de la Triple-Entente (France + Royaume-Uni + Russie) ou de la Triple-Alliance (Allemagne + Autriche-Hongrie + Italie) ?

On considère le code ci-dessous.

from math import *
# from random import *
import matplotlib.pyplot as plt
# import numpy as np
# from scipy.stats import linregress

# Données de type 1
liste_x_1 = [1, 3, 8, 13]
liste_y_1 = [28, 27.2, 37.6, 40.7]

# Données de type 2
liste_x_2 = [2, 3, 10, 15]
liste_y_2 = [30, 26, 39, 35.5]

plt.axis([0, 15, 0, 50]) # Attention [x1, x2, y1, y2]
plt.axis('equal')
plt.xlabel('Caractéristique 1')
plt.ylabel('Caractérstique 2')
plt.title('Représentation des deux types')
plt.grid()
plt.scatter(liste_x_1, liste_y_1, label='type 1')
plt.scatter(liste_x_2, liste_y_2, label='type 2')

plt.scatter(7, 28.4, label='cible')
plt.legend()
plt.show()

table = [['t1', 1, 28], ['t1', 3, 27.2], ['t1', 8, 37.6], ['t1', 13, 40.7], ['t2', 2, 30], ['t2', 3, 26], ['t2', 10, 39], ['t2', 15, 35.5]]
cible = [7, 28.4]
k = 3

def k_plus_proches_voisins(table, cible, k):
    """Revoie la liste des k plus proches voisins de la cible"""
        
    def distance_cible(donnee):
        """ renvoie la distance entre la donnée et la cible, on choisit la distance de Manhattan"""
        
        distance = abs(donnee[1]-cible[0]) + abs(donnee[2]-cible[1])
        
        return distance
    
    table_triee = sorted(table, key=distance_cible)
    
    proches_voisins = []
    
    for i in range(k): 
        proches_voisins.append(table_triee[i])
        
    return proches_voisins

print("La liste des ", k, " plus proches voisins de la cible : ", k_plus_proches_voisins(table, cible, k))

Vous pouvez exécuter ce code directement sur ce trinket.

1. Afficher le résultat de la fonction k_plus_proches_voisins(table, cible, k). Quel est le type de la cible ?

2. Quelle est la valeur de $k$ ?

3. Quelle distance a-t-on utilisée ?

4. Utiliser d'autres valeurs de $k$. Quel est l'effet sur le type de la cible ?

5. Changer la distance. Programmer la distance de Tchebychev. Quel est l'effet sur le type de la cible ?

Le but est d'étudier plus en détail l'exemple qui a servi d'introduction visuelle à l'algorithme des $k$ plus proches voisins.

1. Voici une fonction impor :

   import csv
   def impor(nom):
       lecteur = csv.DictReader(open(nom + '.csv', "r", encoding='utf-8-sig'), delimiter=";")
       return [ligne for ligne in lecteur]
   

   La fonction DictReader du module csv permet d'ouvrir un fichier csv et de créer un itérable de dictionnaires. La première ligne du fichier csv donne l'ensemble des clés des dictionnaires et chaque autre ligne donnera les valeurs d'un dictionnaire.

   Si le fichier csv monty_python.csv est donné par le contenu suivant où chaque élément est séparé par le symbole ;

   nom;prenom
   Graham;Chapman
   John;Cleese
   Terry;Gilliam
   Eric;Idle
   Terry;Jones
   Michael;Palin

   alors l'instruction impor("monty_python") renvoie la liste suivante :

   [{'nom': 'Graham', 'prenom': 'Chapman'}, 
    {'nom': 'John', 'prenom': 'Cleese'},
    {'nom': 'Terry', 'prenom': 'Gilliam'}, 
    {'nom': 'Eric', 'prenom': 'Idle'}, 
    {'nom': 'Terry', 'prenom': 'Jones'}, 
    {'nom': 'Michael', 'prenom': 'Palin'}]

   Expliquer comment utiliser cette fonction afin de récupérer dans une variable nommée combattants la liste des personnages associés à leur force, courage et type ; données initialement dans un fichier personnages.csv accessible ici directement.

   Tester le bon fonctionnement de la fonction avec le fichier personnages.csv accessible ici directement.

   Le fichier personnages.csv téléchargé doit être placé au niveau du répertoire courant de travail de votre IDE.
   Si vous ne connaissez pas le répertoire courant de travail ou si vous voulez placer le fichier csv dans le même répertoire que le fichier .py contenant la fonction impor, il vous suffit tout ou partie du code suivant :

   import os            # import du module permettant d'utiliser les fonctionnalités dépendant du système d'exploitation
   print(os.getcwd())   # Pour afficher le répertoire courant de travail usuel
   os.chdir(os.path.dirname(os.path.abspath(__file__)))  # pour travailler désormais dans le répertoire du fichier python exécuté
   print(os.getcwd())   # pour vérifier le répertoire courant de travail modifié     

2. Proposer une fonction est_personnage qui prend en paramètres une liste de personnages comme celle renvoyée par la fonction de la question précédente et un nom sous forme de chaîne de caractères. Cette fonction renvoie un booléen donnant l'appartenance ou non d'un personnage portant le nom donné comme argument dans cette liste.

   Utiliser cette fonction afin de savoir s'il existe un combattant du nom de "Lis" ?

3. Trier la table des personnages par le type.

   1. La fonction sorted permet de renvoyer une liste triée suivant un critère qui est précisé comme fonction donnée en tant qu'argument de l'attribut key : liste_triee = sorted(liste_initiale, key=fonction_de_critere_prioritaire_de_tri).
      Vous trouverez un exemple d'utilisation dans le deuxième exemple de cette page officielle de la documentation du langage Python.

   2. Vous pouvez utiliser la lambda-fonction lambda x: x["Type"] comme montré dans le cours sur le tri d'une table ou dans la documentation proposée ci-dessus.

4. Écrire et utiliser l'algorithme des $k$ plus proches voisins avec $k=7$ et la distance euclidienne pour savoir quel sera le type du personnage nommé "popsi", de force 12 et de courage 12.5 selon la table des personnages connus.

   1. Vous pouvez compléter et adapter la forme générale du script proposé dans la propriété 2 de ce chapitre.

   2. Pour définir la fonction distance_cible, vous pouvez utiliser la fonction eval. Cette fonction peut prendre une chaîne de caractères correspondant à une expression en Python comme argument et renvoie la valeur calculée pour cette expression (cf. documentation officielle).

À l’entrée à l’école de Poudlard, le Choixpeau magique répartit les élèves dans les différentes maisons (Gryffondor, Serpentard, Serdaigle et Poufsouffle) en fonction de leur courage, leur loyauté, leur sagesse et leur malice.

Le Choixpeau magique dispose d’un fichier CSV dans lequel sont répertoriées les données d’un échantillon d’élèves. Le fichier ChoixpeauMagique.csv est téléchargeable à cet endroit : choixpeauMagique.csv

On souhaite que Choixpeau magique oriente :

On décompose l'exercice en 5 parties :

1. Modéliser un élève
   On modélise un élève par un dictionnaire.
   

   Exemple : {'Nom': 'Bellatrix', 'Courage': 10, 'Loyauté': 4, 'Sagesse': 9, 'Malice': 9, 'Maison': 'Serpentard'}.

   1. Donner la modélisation de l'élève Anthony.

   2. On utilise la distance de Manhattan.

      1. Vérifier à la main que la distance entre Hermione et Adrian est égale à 8.

      2. Quelle est la distance entre Angelina et Drago ?

      3. Écrire le code d'une fonction distance qui prend deux élèves en paramètre et qui renvoie la distance entre ces deux élèves. Ne pas oublier de préciser la documentation et donner au moins un test.

   Code de déblocage de la correction :

2. Charger les données de la table

   Se reporter au chapitre sur les tables afin d'écrire une fonction qui permet de récupérer les données des élèves d'un fichier CSV pour les stocker dans une liste. On doit obtenir une liste de dictionnaires.

   Code de déblocage de la correction :

3. Trouver la maison majoritaire

   1. Écrire une fonction frequence_des_maisons(table) qui prend en paramètre une table d'élèves et qui renvoie le dictionnaire des fréquences des maisons. Vous devez obtenir : {'Serpentar': 12, 'Gryffondor': 17, 'Serdaigle': 11, 'Poufsouffle': 10}.

   2. Écrire une fonction maison_majoritaire(table) qui prend en paramètre une table d'élèves et qui renvoie le nom de la maison la plus représentée.

   Code de déblocage de la correction :

4. Algorithme des 7 plus proches voisins

   On dispose d'une table et d'une nouvelle élève Niue qui n'a pas encore de maison. On sait que cette élève est de "Courage" de niveau 7, de "Loyauté" de niveau 8, 5 en niveau de "Sagesse" et 4 en niveau de "Malice".
   On cherche les 7 plus proches voisins de ce nouveau.

   1. Écrire l'algorithme des 7 plus proches voisins.

   2. Implémenter cet algorithme en python.

   3. Faire un test avec 'Hermione'. Vous devez obtenir les 7 voisins suivants : [{'nom': 'Cormac', 'Courage': 9, 'Loyauté': 6, 'sagesse': 5, 'malice': 4, 'maison': 'Gryffondor'}, {'nom': 'Milicent', 'Courage': 9, 'Loyauté': 3, 'sagesse': 5, 'malice': 6, 'maison': 'Serpentar'}, {'nom': 'Neville', 'Courage': 10, 'Loyauté': 5, 'Sagesse': 6, 'Malice': 4, 'Maison': 'Gryffondor'}, {'nom': 'Padma', 'Courage': 6, 'Loyauté': 6, 'Sagesse': 6, 'Malice': 9, 'Maison': 'Serdaigle'}, {'nom': 'Susan', 'Courage': 5, 'loyauté': 6, 'Sagesse': 5, 'malice': 5, 'Maison': 'Poufsouffle'}, {'nom': 'Angelina', 'Courage': 10, 'loyauté': 6, 'Sagesse': 5, 'Malice': 9, 'Maison': 'Gryffondor'}, {'nom': 'Colin', 'Courage': 10, 'Loyauté': 7, 'Sagesse': 4, 'Malice': 7, 'Maison': 'Gryffondor'}]

      La maison attribuée pour 'Hermione' est 'Gryffondor'.

   Code de déblocage de la correction :

5. Attribuer une maison

   On dispose d'une table et de cette nouvelle élève Niue qui n'a pas encore de maison. On sait que cette élève est de "Courage" de niveau 7, de "Loyauté" de niveau 8, 5 en niveau de "Sagesse" et 4 en niveau de "Malice".
   On cherche désormais à lui attribuer une maison.

   Implémenter en python l'algorithme de l'attribution :

   1. Trouver dans la table les 7 plus proches voisins de cette nouvelle élève.

   2. Parmi ces proches voisins, trouver la maison majoritaire.

   3. Renvoyer la maison majoritaire pour cette élève "Niue".

   Faire un test avec 'Hermione'. Vous devez obtenir comme maison "Gryffondor".